package quick_sort
import (
	"common"
	"fmt"
)

func partition(arr []int, lo int, hi int) int {
	i := lo+1
	j := hi
	v := arr[lo]
	for {
		for arr[i] < v {
			i++
			if i == hi {
				break
			}
		}
		for v < arr[j] {
			j--
			if j == lo {
				break
			}
		}
		if i >= j {
			break
		}
		fmt.Printf("Exch(arr, %d, %d)\n", i, j)
		common.Exch(arr, i, j)
	}
	fmt.Printf("Exch(arr, %d, %d)\n", lo, j)
	common.Exch(arr, lo, j)
	return j
}

func sort(arr []int, lo int, hi int)  {
	if hi <= lo {
		return
	}
	fmt.Printf("partition(arr, %d, %d)\n", lo, hi)
	j := partition(arr, lo, hi);
	sort(arr, lo, j-1)
	sort(arr, j+1, hi)
}

func sort3way(arr []int, lo int, hi int)  {
	if hi <= lo {
		return
	}
	lt := lo
	i := lo+1
	gt := hi
	v := arr[lo]
	for i <= gt {
		if arr[i] < v {
			common.Exch(arr, lt, i)
			lt++
			i++
		} else if arr[i] > v {
			common.Exch(arr, i, gt)
			gt--
		} else {
			i++
		}
		sort3way(arr, lo, lt-1)
		sort3way(arr, gt+1, hi)
	}
}

func Sort(arr []int)  {
	sort3way(arr, 0, len(arr)-1)
}
